package chart.图的遍历;

import chart.图的存储.AbstractGraph;
import chart.图的存储.AdjacencyMatrix;
import chart.图的存储.AdjacencyTable;
import chart.图的存储.Edge;

import java.util.List;

/**
 * 深度优先搜索
 * <p>相当于树的先根遍历</p>
 * <p>可以判断图是否有环</p>
 * <p>算法要点：</p>
 * <p>遍历非连通图, 通过一个 bool 数组记录顶点是否被访问过</p>
 *
 * <p>连通分量数 = dns 的次数</p>
 *
 * <p>空间复杂度: O(n), 递归所需的空间</p>
 *
 * @author yezh
 * @date 2023/7/10 19:14
 */
public class GraphDFS {

    public static void main(String[] args) {
        testAdjacencyMatrix();
        System.out.println();
        testAdjacencyTable();
    }

    private static void testAdjacencyMatrix() {
        // 时间复杂度: O(V * V), 需要遍历整个矩阵
        AbstractGraph graph = new AdjacencyMatrix(6, false);
        graph.createGraph(Edge.graphDFS());
        dfs(graph);
    }

    private static void testAdjacencyTable() {
        // 时间复杂度: O(V + E), 需要遍历顶点和边
        AbstractGraph graph = new AdjacencyTable(6, false);
        graph.createGraph(Edge.graphDFS());
        dfs(graph);
    }

    public static void dfs(AbstractGraph graph) {
        int n = graph.getV();
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++)
            if (!visited[i]) dfs(i, graph, visited);

    }

    private static void dfs(int vertex, AbstractGraph graph, boolean[] visited) {
        visited[vertex] = true;
        System.out.println(vertex);
        List<Edge> edges = graph.getNeighborEdge(vertex);
        for (Edge edge : edges)
            if (!visited[edge.getArcHead()]) dfs(edge.getArcHead(), graph, visited);
    }

}
